package doublePtr

// 时间复杂度：O(n)
// 空间复杂度:O(1)
func nextPermutation(nums []int) {
	if nums == nil || len(nums) == 0 {
		return
	}
	n := len(nums)
	i, j := n-2, n-1
	// 1 3 3 2 如果存在重复数字，则继续左移，因为3对其右边的所有元素来说都是最大的，与右边比自己小的元素交换只能的到更小的序列
	for i >= 0 && nums[i] >= nums[i+1] {
		i--
	}

	// 如果i小于0，则表示整个序列都是递减的，即当前序列为最大序列，只需要反转即可得到最小序列
	if i >= 0 {
		// 这里只能取大于nums[i]的值，不能等于，所以当nums[j]==nums[i]时，仍需要向左移动
		for j >= 0 && nums[i] >= nums[j] {
			j--
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	// 对位置i右边的部分进行逆转
	reverse(nums[i+1:])
}

// 逆转序列
func reverse(nums []int) {
	for i, n := 0, len(nums); i < len(nums)/2; i++ {
		nums[i], nums[n-i-1] = nums[n-i-1], nums[i]
	}
}
